﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<stdbool.h>
using namespace std;
//给你一个大小为 m x n 的二进制矩阵 grid 。
//
//岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
//
//岛屿的面积是岛上值为 1 的单元格的数目。
//
//计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/max-area-of-island
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。



//两种解法: DFS和BFS
class Solution {//DFS
public:
	int maxAreaOfIsland(vector<vector<int>>& grid) {
		vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
		for (int i = 0; i < grid.size(); i++)
		{
			for (int j = 0; j < grid[0].size(); j++)
			{
				int s = 1;
				if (!visited[i][j] && grid[i][j] == 1)
				{
					visited[i][j] = true;
					dfs(grid, visited, i, j, s);
				}
			}
		}
		return smax;
	}
private:
	int dir[4][2] = { 0, 1, 0, -1, -1, 0, 1, 0 };
	vector<int> path;
	int smax = 0;
	void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int& s)
	{
		if (s > smax)
		{
			smax = s;
		}
		for (int i = 0; i < 4; i++)
		{
			int nextx = x + dir[i][0];
			int nexty = y + dir[i][1];
			if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 越界了，直接跳过
			if (!visited[nextx][nexty] && grid[nextx][nexty] == 1)
			{
				visited[nextx][nexty] = true;
				s++;
				dfs(grid, visited, nextx, nexty, s);
				//s--;
			}
		}
	}
};

class Solution {//BFS
private:
	int count;
	int dir[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 }; // 四个方向
	void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
		queue<int> que;
		que.push(x);
		que.push(y);
		visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点
		count++;
		while (!que.empty()) {
			int xx = que.front(); que.pop();
			int yy = que.front(); que.pop();
			for (int i = 0; i < 4; i++) {
				int nextx = xx + dir[i][0];
				int nexty = yy + dir[i][1];
				if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界
				if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地
					visited[nextx][nexty] = true;
					count++;
					que.push(nextx);
					que.push(nexty);
				}
			}
		}
	}

public:
	int maxAreaOfIsland(vector<vector<int>>& grid) {
		int n = grid.size(), m = grid[0].size();
		vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
		int result = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j] && grid[i][j] == 1) {
					count = 0;
					bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
					result = max(result, count);
				}
			}
		}
		return result;
	}
};
int main()
{
	Solution A;
	vector<vector<int>> grid = { {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
								{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
								{0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
								{0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
								{0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
								{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
								{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
								{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0} };
	int e = A.maxAreaOfIsland(grid);
	cout << e;
	return 0;

}

